1. Field
The present invention relates generally to decoding of variable-length codes, e.g., Huffman codes, and, more specifically, to a new decoding scheme based on multiple interconnected lookup tables.
2. Description
Entropy coding is a widely used data compression technique that many video and audio coding standards are based on. The theoretical basis of entropy coding states that a compression effect can be reached when the most frequently used data are coded with a fewer number of bits than the number of bits denoting the less frequently appearing data. This approach results in coded data streams composed of codes having different lengths.
There are a number of methods to form such variable length codes (VLC). One popular method uses a prefixed coding in which a code consists of a prefix that allows a decoding system to distinguish between different codes, and several significant bits representing a particular value (e.g., Huffman coding).
Another method may use postfix coding schemes where variable length bit patterns are appended to the significant bits.
As most coding standards employ Huffman codes and provide statically pre-coded VLC tables for motion picture coding (e.g., ISO/IEC 11172-2, Moving Pictures Experts Group (MPEG)-1 coding standard: Video; ISO/IEC 13818-2, MPEG-2 coding standard: Video; ISO/IEC 14496-2, MPEG-4 coding standard: Visual), it is not always true that the most probable data is coded with the shortest VLCs. Moreover, the probability distributions for particular video streams may have several peaks which means that there may be several code groups comprising VLCs of different lengths that are likely to appear. In this case the variable length decoding methods operating on theoretically predicted probability distributions may have lower performance as compared to methods that can be adapted to the actual VLC probabilities.
Therefore, a need exists for the capability to provide high speed decoding of variable length codes of different origin, in accordance with the actual frequency-to-code length distribution.